package com.mamingchao.foundation.tree.heap;

import java.util.*;

/**
 * Created by mlamp on 2024/5/13.
 * 优先级队列 即用堆的结构实现，默认是小根堆
 * 如果自定义Comparator,  则会按照自定义的对比器规则排序
 */
public class PriorityQueueTest {

    public static void main(String[] args) {
//        MyComparator myComparator = new MyComparator();
//
//        MyHeap<Student> myHeap = new MyHeap(myComparator);
//        PriorityQueue<Student> heap = new PriorityQueue<>(myComparator);
//
//        for (int i = 0; i < 10; i++) {
//            Double randomRoll = Math.random();
//            Double nodeValue = randomRoll*100;
//            Student student = new Student(nodeValue.intValue());
//            myHeap.put(student);
//            heap.add(student);
//        }
//
//        for (int i = 0; i < 7; i++) {
//            myHeap.poll();
//            heap.poll();
//        }
//
//        for (int i = 0; i < 3; i++) {
//            System.out.println(myHeap.poll() + "--" + heap.poll());
//        }








        MyComparator myComparator = new MyComparator();

        ArrayList<Student> existElement = new ArrayList<>();
        //此为系统自带的堆实现，现在只用降序的整型比较器
        PriorityQueue<Student> heap = new PriorityQueue<>(myComparator);
        // 此为自定义的堆，可支持更新某个node value，并重新调整为 堆结构的
        MyHeap<Student> myHeap = new MyHeap(myComparator);

        final int loopCount = 1000;

        Random randomInstance = new Random();

        for (int i = 0; i < loopCount; i++) {

            Double opCountDoubleValue = Math.random() * 5;

            int opCount = opCountDoubleValue.intValue() + 1;

            for (int j = 0; j < opCount; j++) {
                Double randomRoll = Math.random();
                Double nodeValue = randomRoll*100;
                Student student = new Student(i + j);
                // 5分之3的概率，往堆里面放值
                if (randomRoll > 0.4) {

                    if (myHeap.contain(student)){
                        int existRandomIndex = randomInstance.nextInt(myHeap.size());

                        Student existNode = existElement.get(existRandomIndex);
                        heap.remove(existNode);
                        existNode.age = nodeValue.intValue();
                        myHeap.updExistElement(existNode);
                        heap.add(existNode);
                    }


                    if (!myHeap.contain(student)){
                        myHeap.put(student);
                        heap.add(student);
                        existElement.add(student);
                    }


                } else { // 5分之2的概率，从堆里面poll值
                    Student myHeapPollValue = null;
                    Student heapPollValue = null;

                    if (!myHeap.isEmpty())
                        myHeapPollValue = myHeap.poll();

                    if (!heap.isEmpty())
                        heapPollValue = heap.poll();

                    existElement.remove(heapPollValue);

                }
            }
        }

        while (!myHeap.isEmpty() && !heap.isEmpty()){
            System.out.println("剩下的元素，对比-[自定义堆]-" + myHeap.poll() + "-系统自带堆-" +heap.poll());
        }

        System.out.println("@@@@@@@@@@@@@@@@@@@@-"+myHeap.size()+"-@@@@@@@@@@@@@@@@@@@@@@"+heap.size()+"-@@@@@@@@@@@@@@@@@@@@@@");




//        heap.add(3);
//        heap.add(5);
//        heap.add(6);
//        heap.add(1);
//        heap.add(9);
//        heap.add(0);
//        heap.add(-2);

//        while (!heap.isEmpty()) {
//            System.out.println(heap.poll());
//        }

    }


    private static class Student{
        private int age;

        public Student(){

        }

        // 随便定义一个 内部类
        public Student(int age){
            this.age = age;
        }

        @Override
        public String toString(){
            return String.valueOf(age);
        }

    }

    // 自定义 comparetor, 根据比较器，生成堆

    // 整型降序自定义比较器
    private static class MyComparator implements Comparator<Student>{

        @Override
        public int compare(Student o1, Student o2) {
            if (o1.age < o2.age) {
                return 1;
            } else if (o1.age > o2.age) {
                return -1;
            } else {
                return 0;
            }
        }
    }
}
